from libc.stdlib cimport malloc, free
from cpython cimport bool

from pybloomfilter import BloomFilter
import copy

cdef unsigned int DEFAULT_THRESHOLD = 3
cdef unsigned int HASH_BITS = 64

cpdef string_hash(const unsigned char *source):
    cdef unsigned char c
    cdef long m = 1000003
    cdef unsigned long long x, mask
    if len(source) == 0:
        return 0
    else:
        x = source[0] << 7
        mask = 2 ** HASH_BITS - 1
        for c in source:
            x = ((x * m) ^ c) & mask
        x ^= len(source)
        return x

cdef class SimHash:

    cdef public unsigned long long value
    cdef unsigned int hashBits

    def __init__(self, tokens):
        '''
        Initialization.
        Args:
            tokens: Tokens in sentences. eg. tokens = "dive into python".split()
        '''
        tokens = [token.encode('utf-8') if isinstance(token, unicode) else token for token in tokens]
        self.value = self.sim_hash(tokens)

    def __str__(self):
        '''
        String representation of a SimHash instance.
        '''
        return str(self.value)

    cpdef sim_hash(self, tokens):
        '''
        Get a fingerprint of the token list.
        Args:
            tokens: Tokens in sentences. eg. tokens = 'dive into python'.split()
        Returns:
            A fingerprint of the token list.
        '''
        cdef int *v = <int *> malloc(sizeof(int)*HASH_BITS)
        cdef unsigned long long t, bitmask, fingerprint = 0
        cdef unsigned int i
        for i in xrange(HASH_BITS):
            v[i] = 0
        for t in [string_hash(x) for x in tokens]:
            for i in xrange(HASH_BITS):
                bitmask = 1LL << i
                if t & bitmask :
                    v[i] += 1
                else:
                    v[i] -= 1
        for i in xrange(HASH_BITS):
            if v[i] >= 0:
                fingerprint += 1LL << i
        free(v)
        return fingerprint

    cpdef unsigned int hamming_distance(self, SimHash other):
        '''
        Get the hamming distance of this SimHash instance with other SimHash instance.
        Args:
            other: other SimHash instance
        Returns:
            The hamming distance of this SimHash instance with other SimHash instance.
        '''
        cdef unsigned long long x = (self.value ^ other.value)
        cdef unsigned int tot = 0
        while x > 0:
            tot += 1
            x &= x - 1
        return tot

    cpdef bool is_similar_to(self, SimHash other, unsigned int threshold = DEFAULT_THRESHOLD):
        '''
        To caculate whether this SimHash instance is similar to the other SimHash instance.
        Args:
            other: the other SimHash instance
            threshold: hamming distance threshold
        Returns:
            Is similar or not.
        '''
        cdef unsigned long long x = (self.value ^ other.value)
        cdef unsigned int tot = 0
        cdef bool whether_or_not = True
        while x > 0:
            tot += 1
            if tot > threshold:
                whether_or_not = False
                break
            x &= x - 1
        return whether_or_not

    cpdef float similarity(self, SimHash other):
        '''
        Get the similarity between this SimHash instance and other SimHash instance.
        Args:
            other: other SimHash instance
        Returns:
            The similarity between this SimHash instance and other SimHash instance.
        '''
        cdef unsigned int dist = self.hamming_distance(other)
        return 1.0-dist*1.0/HASH_BITS
        
cpdef compact(id_simhash_tup_list, unsigned int threshold = DEFAULT_THRESHOLD, int verbose = 1):
    '''
    Filter the duplicated simhashes.
    Args:
        id_simhash_tup_list: the list of (id, simhash)
        threshold: hamming distance threshold
        verbose: verbose or not
    Returns:
        The none duplicated simhashs.
    Example:
        >> id_simhash_tup_list = []
        >> for i in xrange(0, 10000, 2):
               id_simhash_tup_list.append((i, SimHash('Dive into Python'.split())))
               id_simhash_tup_list.append((i+1, SimHash('Python cookbook'.split())))
        >> for key, content in compact(id_simhash_tup_list):
               print key, ' '.join(content)
    '''
    copyof_id_simhash_tup_list = copy.copy(id_simhash_tup_list)
    cdef unsigned int i = 0
    cdef unsigned int length = len(copyof_id_simhash_tup_list)
    while i < length:
        if verbose > 0 and i % 100 == 0:
            print 'compacting', i, '/', length
        copyof_id_simhash_tup_list[i+1:] = get_unduplicated(copyof_id_simhash_tup_list[i], copyof_id_simhash_tup_list[i+1:])
        i += 1
        length = len(copyof_id_simhash_tup_list)
    return copyof_id_simhash_tup_list

cpdef fast_compact(id_simhash_tup_list, capacity = 10000000, error_rate = 0.0005, filename = '/tmp/bloomfilter', verbose = 1):
    '''
    Filter the duplicated simhashes using bloom filter.
    Args:
        id_simhash_tup_list: the list of (id, simhash)
        capacity: one of bloomfilter's args, default 10000000
        error_rate: one of bloomfilter's args, default 0.0005
        filename: one of bloomfilter's args, default '/tmp/bloomfilter'
        verbose: verbose or not
    '''
    hashes = BloomFilter(capacity, error_rate, filename)
    remained = [id_simhash_tup_list[0], ]
    hashes.add(id_simhash_tup_list[0][0])
    cdef unsigned int length = len(id_simhash_tup_list)
    cdef unsigned int i = 0
    for key, sh in id_simhash_tup_list:
        if not hashes.add(sh.value):
            remained.append((key, sh))
        if verbose > 0 and i % 100 == 0:
            print 'compacting', i, '/', length
        i += 1
    return remained    
    
cpdef get_unduplicated(id_simhash_tup, id_simhash_tup_list, unsigned int threshold = DEFAULT_THRESHOLD):
    simhash0 = id_simhash_tup[1]
    remained = []
    for key, simhash1 in id_simhash_tup_list:
        if not simhash0.is_similar_to(simhash1, threshold):
            remained.append((key, simhash1))
    return remained